1. Field of the Invention
The present invention relates to the design of digital circuits. More specifically, the present invention relates to a method and an apparatus for asynchronously distributing data to multiple destinations within a digital circuit.
2. Related Art
Finite state machines are familiar to every designer of computer equipment. They are easy to describe and generally easy to implement. Such a machine can be in any one of a number of xe2x80x9cstatesxe2x80x9d. Most implementations use a set of xe2x80x9cstate flip-flopsxe2x80x9d to hold the present state of the finite state machine.
For each state there are a set of conditions that will cause the finite state machine to change from that state to some other state. The conditions examined in each state may be unique to that state or shared with other states. The state to which the device changes depends on the state it is in, the conditions examined in that state, and which conditions are TRUE.
For example, a simple up-down counter is a finite state machine. Its states are the finite number of count values that it can hold. The conditions examined in each state are xe2x80x9ccount upxe2x80x9d and xe2x80x9ccount downxe2x80x9d. The up-down counter advances from its present state to the next higher count value when it gets the xe2x80x9ccount upxe2x80x9d condition and advances to the next lower count value when it finds the xe2x80x9ccount downxe2x80x9d condition. Depending on the design it may have a highest state in which it can only count down or a lowest state in which it can only count up or both.
Finite state machines typically use externally-clocked flip-flops to hold their state. Logic elements examine the conditions pertinent to the present state, and upon the arrival of each external clock pulse, set or clear selected clocked flip-flops to establish the next state. The design of such externally-clocked finite state machines is relatively easy, because all flip-flops change, if at all, only in response to the same external clock signal. Thus, for example, it is acceptable to change the state of several flip-flops at once, for example as happens in a binary counter when the xe2x80x9ccarryxe2x80x9d passes through several stages, returning them all to the xe2x80x9czeroxe2x80x9d state. Were the flip-flops of the counter not clocked externally, the process of changing several flip-flops might cause the counter for a short interval to assume one or more intermediate states outside the proper binary sequence.
Indeed, some simple finite state machines, including binary counters are often built without an external clock for their flip-flops. In such counters, called xe2x80x9cripple counters,xe2x80x9d the state flip-flops that hold the count each act independently. The flip-flop holding each bit of the count changes its state in response to changes from xe2x80x9conexe2x80x9d to xe2x80x9czeroxe2x80x9d in the flip-flop that holds the bit representing half its value. Thus, for example, when a six bit ripple counter changes from 001111 to 010000, it will momentarily assume the states 001110, 001100, 001000, 010000 in rapid succession even though they are out of sequence. It is well known to those familiar with ripple counters that one must exercise care in their application because such FALSE states appear in their flip-flops, albeit for very short intervals of time. For finite state machines of any complexity, the simplicity of externally-clocked flip-flops is much preferred.
One aspect of all finite state machines involves the mapping of the allowed states of the machine onto the possible states of the flip-flops that retain the state. Such a mapping is called the xe2x80x9cstate encodingxe2x80x9d used for the finite state machine because it defines the meaning of each possible state of the flip-flops. The encoding may also rule out certain combinations of flip-flop states as outside the range permitted for that finite state machine.
There are two particularly simple encodings. First, some finite state machines use a xe2x80x9cone-out-of-Nxe2x80x9d encoding in which only one state flip-flop is xe2x80x9csetxe2x80x9d for each state. This encoding rules out the state with no state flip-flops set as well as all states with more than one state flip-flop set. With the one-out-of-N encoding, each change of state sets the state flip-flop associated with the new state and clears the state flip-flop associated with the old state. The one-out-of-N state encoding, though simple, is impractical for finite state machines with large numbers of states.
A second simple state encoding is a binary state encoding. In this state encoding each state is defined by a binary combination of state flip-flops that are set and that are clear. The binary encoding permits all combinations. This encoding is suitable for some finite state machines such as the binary counter already mentioned. It has the problem, however, that some state changes may require simultaneously setting many state flip-flops and clearing many others. The need to change many state flip-flops simultaneously renders binary encoding unsuitable for some applications. Designers have learned to choose encodings suitable to the needs of each particular application.
Finite state machines use complex logic elements to control the set and clear functions of individual flip-flops. These conditions cause xe2x80x9ctransitionsxe2x80x9d in the state of the finite state machine. The collection of conditions that must be TRUE to cause a particular transition must first be combined by a logical AND function. The output of this logic function will be TRUE when all relevant conditions are TRUE. Such a function indicates an impending state transition. Next, depending on the particular encoding used, several state flip-flops may have to change for such a state transition, some being set and some being cleared. The state transition logic must deliver its output to all such state flip-flops. Finally, it is likely that several transition functions apply to some state flip-flops. Such multiple transition functions must be combined with logical OR circuits to drive the inputs of the externally-clocked state flip-flops.
In spite of the complexity of such finite state machine implementations, they are so familiar to designers today that they are widely used. Indeed there are even computer automated design methods to help designers develop the required logic from equations describing the desired behavior. The software commonly used to design finite state machines depends on the use of externally-clocked flip-flops as the medium for holding the state.
The methods currently in use for designing finite state machines evolved over a long period of time. They were developed initially for use in machines built from vacuum tubes or even earlier for machines built from relays. They have served well into the era of transistor machines, but only to the extent that the more modern technologies are used in ways similar to those of the older technologies. Thus, the use of clocked flip-flops to hold state, for example, is a form that has survived several changes in the circuit elements and circuits used to implement such flip-flops.
Now, however, most digital computing devices use complementary metal oxide semiconductor (CMOS) circuits. In current CMOS circuits the cost of wires rather than the cost of logic gates dominates area, power consumption and performance. Almost all the space in a modern CMOS circuit is occupied by interconnect wiring; the transistors forming the logic gates generally fit underneath the wires required to interconnect them. The power consumption of the circuit is dominated by the need to put electrical charge onto the wires and later to remove it. The performance of the circuits is limited largely by the time it takes to charge and discharge the wires.
Moreover, in CMOS circuits, electrical capacitance can serve a state-holding function that previously had to be done with logic elements formed into flip-flops. Indeed, the dynamic random access memory (DRAM) industry has honed to a fine level the use of capacitance to store information. In a DRAM the electrical charge stored on a tiny capacitor serves to record each bit of information. However, in other CMOS circuits, the charge on any wire can also serve to store information.
Designers use such electrical charges stored on wires in making xe2x80x9cdynamicxe2x80x9d circuits. Dynamic circuits depend for their operation on the retention of information in electrical charges on wires. Dynamic circuits are possible in CMOS because the control input of a CMOS transistor, the xe2x80x9cgatexe2x80x9d of the transistor, operates on charge rather than current. An electric charge placed on the gate of a transistor will continue to condition the behavior of the transistor for a relatively long period until the charge gradually xe2x80x9cleaksxe2x80x9d off.
Note that a fundamental building block for a dynamic circuit is a distributor that distributes data from a single source to a number of destinations.
The present invention uses such dynamic charge storage as the basis for a variety of finite state machines. It notes that charge placed on a CMOS conductor that connects to a number of transistor gates will condition those gates, and continue to do so for a relatively long time. Instead of storing the state of a finite state machine in a collection of state flip-flops, the present invention stores the state of a finite state machine on a set of state conductors, using the capacitive charge on those conductors to hold the state.
Unlike a state flip-flop, which is geometrically local, such a state conductor can be distributed geometrically over a wide area. It can be extended to whatever length is desired, turn corneers or branch as needed, and can connect together as many components as desired. To change the state of a state flip-flop requires bringing the output of the transition logic to the state flip-flop. A state transition wire connects from the state transition logic to the state flip-flop. In contrast, to change the charge on a state conductor requires only that the state conductor be driven to the new state from anywhere along its length. The state conductor will automatically communicate the new state throughout its length.
Moreover in CMOS technology a state conductor will retain its charge state for a relatively long time. If the state must be retained indefinitely, a small xe2x80x9ckeeperxe2x80x9d can be attached to the wire. Such a keeper gently drives the wire towards its most positive state if it is already positive and gently drives it towards its most negative state if it is already negative. The keeper is sufficiently weak that it is unable to resist the intentional state changes imposed by operation of the finite state machine, but just strong enough to counteract the tiny leakage currents and the effects of electrical xe2x80x9cnoisexe2x80x9d that might otherwise disturb the charge stored on the conductor and thus improperly change its state.
Another advantage of using the charge on a state conductor to store state is the ability to use individual transistors to change its charge state. We will call such transistors xe2x80x9cdrive transistors.xe2x80x9d The two types of transistors used in CMOS circuits, N-type and P-type, drive their outputs in different directions. One or more N-type drive transistors connected anywhere along the length of a state conductor can drive it to the xe2x80x9cLOxe2x80x9d state, and likewise one or more P-type drive transistors connected anywhere along the state conductor can drive it to the xe2x80x9cHIxe2x80x9d state. Because the drains of these drive transistors each contribute capacitance to the conductor, attaching them to the conductor actually increases the ability of the conductor to store charge, thus enhancing its ability to retain state!
Moreover, if several transition conditions each must cause the state to change, several separate N-type or P-type drive transistors can be attached to the state conductor to condition it properly. The conductor goes to the LO state in response to any N-type drive transistor anywhere along its length. Likewise the conductor goes to the HI state in response to any P-type drive transistor anywhere along its length. State conductors will often accommodate more than one N-type and more than one P-type drive transistor.
It is important, however, that the N-type drive transistors and the P-type drive transistors for a single state conductor must never act simultaneously. Simultaneous drive by both types of drive transistors would represent a logical conflict, some attempting to make the state conductor HI and some attempting to make it LO. Were such conflict to occur, two bad things would happen. First, excess current would flow from the power supply to ground, consuming energy unnecessarily. Second, the charge left on the conductor might be uncertain, it not having been certain which should prevail, the N-type drive transistors, yielding the LO state, or the P-type drive transistors, yielding the HI state.
The present invention addresses this requirement to avoid conflicting drivers. Each state transition will occur when one or more N-type drive transistors connected to a particular state conductor act or one or more P-type drive transistors connected to that state conductor act. Of course, depending on the encoding chosen, several state conductors might change state at the same time, some driven by N-type drive transistors and others by P-type drive transistors, as required by the design. However, in no case will both the N-type and P-type drive transistors of a single state conductor act together.
Consider also energy consumption, another matter addressed by the present invention. In CMOS circuits a principle consumption of energy is to charge and discharge the capacitance of wires. The amount of energy consumed for an action, charging or discharging a wire, involves the capacitance of the wire which depends, of course, on its length. Thus the power consumed depends on how many charge and discharge cycles happen per unit of time and upon the length of the wires thus charged or discharged.
In a CMOS finite state machine that uses externally-clocked flip-flops there are three consumers of energy. First, the wires that carry the external clock connect to each of the state flip-flops. These clock wires charge and discharge each clock cycle, whether or not the state of the machine changes. Second, the transition wires that deliver transition commands to the flip-flops extend from the sources of the conditions to the state flip-flop. The transition wires charge and discharge in response to the transition logic. Each transition wire assumes one state before its transition can occur and returns to a neutral state after its transition, two changes per transition. Finally, the wires that report the state of the state flip-flop must extend from the state flip-flop to whatever circuits require knowledge of its state. These state flip-flop output wires change once per state transition.
In a CMOS finite state machine according to the present invention, however, the situation is quite different. First, there is no external clock, which eliminates the space and the energy consumed by the clock wires. Second, rather than localizing the state in the state flip-flops, the present invention distributes the state geometrically over the state conductors. Just as the output wires of state flip-flops extend to whatever needs knowledge of the state of the state flip-flops, the state conductor extends to wherever knowledge of the state is needed. Third, in contrast to systems using state flip-flops, the present invention extends the state conductor to the state transition logic rather than having a separate wire connecting the state transition logic to the state flip-flop. The length of wire required to extend the state conductor to the state transition logic is never longer that the transition wire would have been, and may be much shorter because it need run only from the transition logic to the nearest part of the existing state conductor. Moreover, this wire charges or discharges only once for each state transition rather than twice, thus saving energy.
Hence, instead of using two wires, one to carry transition information to the state flip-flop input and one to carry the state flip-flop output to where it is needed, the present invention uses only one wire, the state conductor, for both purposes. Drive transistors connected anywhere along the length of the state conductor change its state as needed. This reduction in complexity reduces both the total amount of wire required to implement the finite state machine and the energy consumed as it operates.
One embodiment of the present invention provides a system that asynchronously distributes data to a plurality of destinations within a digital circuit. Upon receiving a data item to be distributed, the system monitors asynchronous control signals associated with the destinations, wherein a given asynchronous control signal indicates that a given destination is free to receive the data item. For each destination that is free to receive the data item, the system forwards the data item to the destination asynchronously without waiting for a system clock signal, and also changes an asynchronous control signal associated with the destination to indicate that the destination is not free to receive a subsequent data item.
In one embodiment of the present invention, the system uses a keeper circuit coupled to each asynchronous control signal to hold the asynchronous control signals at a stable value. In a variation on this embodiment, the system changes the asynchronous control signal by generating a pulse to change the asynchronous control signal. (This pulse can be generated through a cycle of logical inversions.)
In one embodiment of the present invention, the system additionally updates the asynchronous control signals so that the plurality of destinations receive successive data items in round-robin order.
In one embodiment of the present invention, the system additionally updates the asynchronous control signals so that the data item is communicated to a destination specified by an address associated with the data item. In a variation on this embodiment, the system communicates the data item by passing the data item through a pipeline, wherein each stage in the pipeline is coupled with a specific destination.
In one embodiment of the present invention, there exist two destinations, and the system updates the asynchronous control signals so that the two destinations receive successive data items in alternating order.
In one embodiment of the present invention, after a given destination receives the data item, the system forwards the data item from the given destination to a downstream location. The system also changes an asynchronous control signal associated with the given destination to indicate that the given destination is again free to receive a subsequent data item.
In one embodiment of the present invention, the plurality of asynchronous control signals propagate between a plurality of pulse circuits that operate a plurality of pass gates, which route the data item to the destinations. In a variation on this embodiment, each pulse circuit includes a first input and a second input that receive asynchronous control signals, and each pulse circuit is configured to fire a pulse to open an associated pass gate when the first input and the second input are both asserted.
In one embodiment of the present invention, the plurality of pass gates includes, a first pass gate that is configured to receive the data item, and a plurality of destination pass gates that are coupled with the plurality of destinations. Furthermore, the plurality of pulse circuits includes, a first pulse circuit that is configured to control the first pass gate, and a plurality of destination pulse circuits that are configured to control the plurality of destination pass gates. In this embodiment, the plurality of asynchronous control signals are coupled between the plurality of pulse circuits so as to control the plurality of pass gates, and to thereby control distribution of the data item to the plurality of destinations.